package search;

/**
 * Created by huangyx on 2017/8/14 0014.
 */
public class RedBlackBST<Key extends Comparable<Key>, Value> {

    private Node root;

    private static final boolean RED = true;
    private static final boolean BLACK = false;

    private class Node {
        Key key;    //键
        Value value;    //相关联的值
        Node left, right;   //左右子树
        int N;      //这棵子树中的结点总数
        boolean color;  //由其父结点指向它的链接的颜色

        Node(Key key, Value value, int n, boolean color) {
            this.key = key;
            this.value = value;
            N = n;
            this.color = color;
        }
    }

    private boolean isRed(Node x) {
        return x != null && x.color == RED;
    }

    private int size(Node x) {
        if (x == null)
            return 0;
        else
            return x.N;
    }

    private void flipColors(Node h) {
        h.color = RED;
        h.left.color = BLACK;
        h.right.color = BLACK;
    }

    private Node rotateLeft(Node h) {
        //左旋
        Node x = h.right;
        h.right = x.left;
        x.left = h;
        x.color = h.color;
        h.color = RED;
        x.N = h.N;
        h.N = 1 + size(h.left) + size(h.right);
        return x;
    }

    private Node rotateRight(Node h) {
        //右旋
        Node x = h.left;
        h.left = x.right;
        x.right = h;
        x.color = h.color;
        h.color = RED;
        x.N = h.N;
        h.N = 1 + size(h.left) + size(h.right);
        return x;
    }

    public void put(Key key, Value value) {
        root = put(root, key, value);
        root.color = BLACK;     //根结点始终黑色
    }

    private Node put(Node h, Key key, Value value) {
        if (h == null)
            return new Node(key, value, 1, RED);
        int cmp = key.compareTo(h.key);
        if (cmp < 0)
            h.left = put(h.left, key, value);
        else if (cmp > 0)
            h.right = put(h.right, key, value);
        else
            h.value = value;
        //与二叉树不同的是红黑树会对元素进行旋转从而达到平衡
        if (isRed(h.right) && !isRed(h.left))
            h = rotateLeft(h);      //如果右子结点是红色而左子结点是黑色，进行左旋
        if (isRed(h.left) && isRed(h.left.left))
            h = rotateRight(h);     //如果左子结点是红色且它的左子结点也是红色，进行右旋
        if (isRed(h.left) && isRed(h.right))
            flipColors(h);          //如果左右子结点均为红色，进行颜色转换
        h.N = size(h.left) + size(h.right) + 1;
        return h;
    }

}
